Heap ヒープ
以下のルールを満たす
二分木 Binary Tree
の
データ構造 Data Structure
親
ノード Node
の値は子ノードの値以上
木のノード番号が一番大きいノードより若い番号のノードはすべて存在
ノード Node
の親子関係
ノード k の子供は、2k+1,2k+2
ノード k の親は、(k−1)/2 (余りは切り捨て)
特徴
table:heap
処理内容 計算時間 備考
配列に値 v を追加
O(log n)
追加してもヒープ状態を保つ
配列から最大値を削除
O(log n)
ルートを消して木を整える
配列内の最大値を知る
O(1)
二分木のルート (ノード 0) 値
利点
データ数に関係なく
O(1)
で取り出すこと可能
常に
root 根
に最大値(最小値)が格納されているため
欠点
データの追加、取り出しをした場合
再構築必要
TODO:実装がまだちゃんとできてない
💯
ソートを極める! 〜 なぜソートを学ぶのか 〜 - Qiita
特徴の説明がわかりやすい!!